package demo3;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-07-02
 * Time: 17:09
 */
public class TestDemo2 {

    /** 在一个数组中，一个数左边比它小的数的总和，叫该数的小和
    所有数的小和累加起来，叫数组小和
    * 例子： [1,3,4,2,5] 1左边比1小的数：没有 3左边比3小的数：
    * 1 4左边比4小的数：1、3 2左边比2小的数：
    * 1 5左边比5小的数：1、3、4、 2 所以数组的小和为1+1+3+1+1+3+4+2=16
    * 给定一个数组arr，求数组小和
    */

    public static int func(int[] arr){
        int cnt =0;

        for(int i =1;i<arr.length;++i){
            for(int j = i-1;j>=0; --j){
                if(arr[i]>arr[j]){
                    cnt+=arr[j];
                }
            }
        }
        return cnt;
    }

    public static int merge(int[] arr,int left,int mid,int right){
         int b1 = left;
         int b2 = mid+1;
         int[] tmp = new int[right - left+1];
         int k =0;
         int res =0;
         //找一个数的左边比这个数字小的数字的和
        //转化为一个数的右边有几个数字比这个数字大
        //1 2 2 3  3 4 4 5
         while(b1<=mid&&b2<=right){
             res += arr[b1]< arr[b2]?(right-b2+1)*arr[b1]: 0;
             tmp[k++] = arr[b1]<arr[b2]? arr[b1++]:arr[b2++];
         }
         while(b1<=mid){
             tmp[k++] = arr[b1++];
         }
         while(b2<=right){
             tmp[k++] = arr[b2++];
         }
         //拷贝回原来数组
        for(int i =0;i<tmp.length;++i){
            arr[left+i] = tmp[i];
        }
        return res;
    }


    public static int process(int[] arr,int left,int right){
        if(left>=right) return 0;
        int mid = left+((right-left)>>>1);
        return process(arr,left,mid)+process(arr,mid+1,right)
                +merge(arr,left,mid,right);
    }

    public static int smallSum(int[] arr){
        return process(arr,0,arr.length-1);
    }

    public static int[] generateRandomArray(int maxSize,int maxValue){
        int[] arr = new int[(int)((maxSize+1)*Math.random())];
        for(int i =0;i<arr.length;++i){
            arr[i] = (int)((maxValue+1)*Math.random())-
                    (int)((maxValue+1)*Math.random());
        }
        return arr;
    }


    //写一个对数器
    public static void main(String[] args) {
        int testTime = 200000;
        int maxValue = 100;
        int maxSize = 100;
        System.out.println("测试开始！！");
        for(int i =0;i<testTime;++i){
            int[] arr1 = generateRandomArray(maxSize,maxValue);
            int[] arr2 = Arrays.copyOf(arr1,arr1.length);
            if(func(arr2)!=smallSum(arr1)){
                System.out.println("出错！！！");
                System.out.println(Arrays.toString(arr1));
                System.out.println(Arrays.toString(arr2));
                break;
            }
        }
        System.out.println("测试结束！！");
    }





    public static void main1(String[] args) {
        int[] arr = {5,2,8,3};
        //5 +2+2
        int ret = func(arr);
        System.out.println(ret);
    }


}
